package data_structure.leetcode;

import data_structure.mooc.QuickSort;

import java.util.Arrays;
import java.util.Random;

public class SolutionOffer40 {

    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0)return new int[0];
        selectK(arr,k,0,arr.length-1);
        return Arrays.copyOf (arr,k);
    }

    private void selectK(int[] arr, int k, int left,int right){

        if(left>=right)return;
        int partition=partition (arr,left,right);
        if(k==partition){
            return;
        }else if(k<partition){
            selectK (arr,k,left,partition-1);
        }else{
            selectK (arr,k-partition,partition+1,right);
        }
    }


    private int partition (int []arr,int left,int right) {

        Random random = new Random ();
            int partition = left + random.nextInt (right - left + 1);
            swap (arr, left, partition);
            int i = left + 1;
            int j = right;

            while(true){
                while(i<=j&&arr[i]<arr[left]){
                    i++;
                }
                while(i<=j&&arr[j] > arr[left]){
                    j--;
                }
                if(i>=j){
                    break;
                }
                swap (arr,i,j);
                i++;
                j--;
            }
            swap (arr,left,j);
            return j;
    }

    private void swap(int []arr,int left,int right){
        int temp=arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}
